#pragma once
#include <cstddef>
#include <utility>
#include <vector>
template<class T>
class Less
{
public:
    bool operator()(const T &x, const T &y)
    {
        return x < y;
    }
};

template<class T>
class Greater
{
public:
    bool operator()(const T &x, const T &y)
    {
        return x > y;
    }
};
template<class T, class Container = std::vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
    priority_queue() = default;
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
        : con_(first, last)
    {
        for (size_t i = (con_.size() - 1 - 1) / 2; i >= 0; --i)
        {
            adjust_down(i);
        }
    }
    void adjust_up(int child)
    {
        Compare com;
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            // if (con_[child] > con_[parent])
            if (com(con_[child], con_[parent]))
            {
                std::swap(con_[child], con_[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
                break;
        }
    }
    void adjust_down(int parent)
    {
        int child = parent * 2 + 1;
        while (child < con_.size())
        {
            if (child + 1 < con_[child + 1] > con_[child])
                ++child;
            if (con_[child] > con_[parent])
            {
                std::swap(con_[child], con_[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
                break;
        }
    }
    void push(const T &value)
    {
        con_.push_back(value);
        adjust_up(con_.size() - 1);
    }
    bool empty() const
    {
        return con_.empty();
    }
    T top()
    {
        return con_.back();
    }
    void pop()
    {
        con_.pop_back();
    }
    ~priority_queue()
    {}

private:
    Container con_;
};